#ifndef _CG_UNION_FIND_H
#define _CG_UNION_FIND_H

template<typename T> class UnionFind
{
	//====
	// internal structures and data members

	struct DataNode {
		T data;
		DataNode *link;
	};

	struct EqualSet {
		DataNode *head, *tail;
		EqualSet *next;
	} *first, *last;

	// this pointer is used to keep track of the node
	// before what's returned by the find function so
	// that the merge routine can reset its next link
	mutable EqualSet *cache;

	int dataCount;

	//====
	// helper functions

	EqualSet *find(const T &t) const
	{
		for (EqualSet *i = first; i; i = i->next) {
			for (DataNode *j = i->head; j; j = j->link) {
				if (j->data == t) {
					return i;
				}
			}
			cache = i;
		}
		return 0;
	}

	void merge(EqualSet *p, EqualSet *s);

	void append(EqualSet *p, const T &t);

	//====
	// forbidden operations

	UnionFind(const UnionFind<T> &u);

	UnionFind<T> &operator =(const UnionFind<T> &u);

public:

	UnionFind() : first(0), last(0), cache(0), dataCount(0) {}

	~UnionFind() { clear(); }

	int size() const { return dataCount; }

	bool empty() const { return !dataCount; }

	bool allEqual() const { return first && first == last; }

	bool equal(const T &t1, const T &t2) const
	{
		EqualSet *i = find(t1);
		return i && i == find(t2);
	}

	void setEqual(const T &t1, const T &t2);

	void insert(const T &t);

	void clear();

};

template<typename T> void UnionFind<T>::insert(const T &t)
{
	if (!find(t)) {
		// create a new "equal set"
		cache = new EqualSet;
		cache->head = cache->tail = new DataNode;
		cache->head->data = t;
		cache->head->link = 0;
		// and add it to the list
		if (!last) {
			first = last = cache;
		} 
		else {
			last = last->next = cache;
		}
		last->next = 0;
		++dataCount;
	}
}

template<typename T> void UnionFind<T>::merge(EqualSet *i, EqualSet *j)
{
	if (i != j) {
		// concatenate the two sets
		i->tail->link = j->head;
		i->tail = j->tail;
		// and update the list
		if (j == first) {
			first = j->next;
		} 
		else {
			cache->next = j->next;
			if (j == last) {
				last = cache;
			}
		}
		delete j;
	}
}

template<typename T> void UnionFind<T>::append(EqualSet *i, const T &t)
{
	i->tail->link = new DataNode;
	i->tail = i->tail->link;
	i->tail->data = t;
	i->tail->link = 0;

	++dataCount;
}

template<typename T> void UnionFind<T>::setEqual(const T &t1, const T &t2)
{
	EqualSet *i = find(t1), *j = find(t2);

	if (!i && !j) {		// both are new
		insert(t1);
		append(last, t2);
	} 
	else if (!i) {		// only t1 is new
		append(j, t1);
	} 
	else if (!j) {		// only t2 is new
		append(i, t2);
	} 
	else {				// neither is new
		merge(i, j);
	}
}

template<typename T> void UnionFind<T>::clear()
{
	while (cache = first) {
		first = first->next;
		while (cache->tail = cache->head) {
			cache->head = cache->head->link;
			delete cache->tail;
		}
		delete cache;
	}

	first = last = cache = 0;
	dataCount = 0;
}

#endif // _CG_UNION_FIND_H
